package com.yanceysong.codetop.s21_s30;

import com.yanceysong.common.ListNode;

/**
 * @ClassName S22_Easy_141_环形链表
 * @Description
 * @date 2024/6/5 下午3:36
 * @Author yanceysong
 * @Version 1.0
 */
public class S22_Easy_141_环形链表 {
    /**
     * S22_Easy_141_环形链表
     * <p>
     * <a href="https://leetcode.cn/problems/linked-list-cycle/">...</a>
     * <p>
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     * <p>
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
     * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）
     * 。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     * <p>
     * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     * <p>
     * 示例：
     * <p>
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     * <p>
     * 输入：head = [1,2], pos = 0
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * <p>
     * 输入：head = [1], pos = -1
     * 输出：false
     * 解释：链表中没有环。
     * <p>
     * 提示：
     * <p>
     * 链表中节点的数目范围是 [0, 10^4]
     * -10^5 <= Node.val <= 10^5
     * pos 为 -1 或者链表中的一个 有效索引 。
     * <p>
     * 使用快慢指针（Floyd's Cycle Detection Algorithm）检测链表中是否有环
     * <p>
     * 算法原理：龟兔赛跑算法（Floyd判圈算法）
     * - 使用两个指针：slow（慢指针，每次移动1步）和fast（快指针，每次移动2步）
     * - 如果链表中有环，快指针最终会追上慢指针
     * - 如果链表中没有环，快指针会先到达链表末尾（null）
     * <p>
     * 为什么快慢指针一定会相遇？
     * 1. 假设环的长度为L，慢指针进入环时，快指针已经在环中某个位置
     * 2. 设此时快指针与慢指针的距离为d（0 ≤ d < L）
     * 3. 每一轮移动后，快指针与慢指针的距离减少1（快指针比慢指针多走1步）
     * 4. 经过d轮后，距离变为0，即两指针相遇
     * <p>
     * 图解示例：
     * <p>
     * 情况1：无环链表
     * 初始状态：
     * slow→ 1 → 2 → 3 → 4 → null
     * fast→ 1 → 2 → 3 → 4 → null
     * <p>
     * 第1步：
     * slow     → 2 → 3 → 4 → null
     * fast          → 3 → 4 → null
     * <p>
     * 第2步：
     * slow          → 3 → 4 → null
     * fast               → null (fast到达末尾，无环)
     * <p>
     * 情况2：有环链表 [3,2,0,-4] with pos=1
     * 链表结构：3 → 2 → 0 → -4
     * ↑         ↓
     * ←---------←
     * <p>
     * 初始状态：
     * slow→ 3 → 2 → 0 → -4
     * fast      ↑    ↓     ↑
     * ←----←-----←
     * <p>
     * 第1步：slow在节点2，fast在节点0
     * slow     → 2 → 0 → -4
     * fast          ↑    ↓     ↑
     * ←----←-----←
     * <p>
     * 第2步：slow在节点0，fast在节点2
     * slow          → 0 → -4
     * fast      → 2    ↓     ↑
     * ↑ ←----←-----←
     * <p>
     * 第3步：slow在节点-4，fast在节点-4（相遇！）
     * slow               → -4
     * fast               → -4 (slow == fast，检测到环)
     * <p>
     * 时间复杂度：O(n)，其中n为链表长度
     * - 无环情况：最多遍历n个节点
     * - 有环情况：慢指针最多走n步进入环，然后在环中最多走环长度的步数
     * <p>
     * 空间复杂度：O(1)，只使用了两个指针变量
     */
    public boolean hasCycle(ListNode head) {
        // 边界条件检查：空链表或只有一个节点且无环
        if (head == null || head.next == null) {
            return false;
        }

        // 初始化快慢指针
        // 慢指针从头开始，每次移动1步
        ListNode slow = head;
        // 快指针从第二个节点开始，每次移动2步
        // 这样可以避免初始时slow == fast的情况
        ListNode fast = head.next;

        // 当快慢指针不相等时继续循环
        while (slow != fast) {
            // 如果快指针或快指针的下一个节点为null，说明到达链表末尾，无环
            if (fast == null || fast.next == null) {
                return false;
            }
            // 慢指针移动1步
            slow = slow.next;
            // 快指针移动2步
            fast = fast.next.next;
        }

        // 循环结束，说明slow == fast，检测到环
        return true;
    }

    public static void main(String[] args) {
        S22_Easy_141_环形链表 solution = new S22_Easy_141_环形链表();

        System.out.println("=== 环形链表检测测试开始 ===");

        // 测试1: 有环链表 - 题目示例1 [3,2,0,-4] pos=1
        System.out.println("\n--- 测试1: 有环链表 [3,2,0,-4] pos=1 ---");
        testCycleCase1(solution);

        // 测试2: 有环链表 - 题目示例2 [1,2] pos=0
        System.out.println("\n--- 测试2: 有环链表 [1,2] pos=0 ---");
        testCycleCase2(solution);

        // 测试3: 无环链表 - 题目示例3 [1] pos=-1
        System.out.println("\n--- 测试3: 无环链表 [1] pos=-1 ---");
        testNoCycleCase1(solution);

        // 测试4: 空链表
        System.out.println("\n--- 测试4: 空链表 ---");
        testEmptyList(solution);

        // 测试5: 单节点无环
        System.out.println("\n--- 测试5: 单节点无环 ---");
        testSingleNodeNoCycle(solution);

        // 测试6: 单节点有环（self-loop）
        System.out.println("\n--- 测试6: 单节点有环 ---");
        testSingleNodeWithCycle(solution);

        // 测试7: 长链表无环
        System.out.println("\n--- 测试7: 长链表无环 ---");
        testLongListNoCycle(solution);

        // 测试8: 长链表有环
        System.out.println("\n--- 测试8: 长链表有环 ---");
        testLongListWithCycle(solution);

        // 测试9: 环在链表开头
        System.out.println("\n--- 测试9: 环在链表开头 ---");
        testCycleAtHead(solution);

        // 测试10: 环在链表末尾
        System.out.println("\n--- 测试10: 环在链表末尾 ---");
        testCycleAtTail(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试有环链表 - [3,2,0,-4] pos=1
     * 链表结构：3 → 2 → 0 → -4
     * ↑         ↓
     * ←---------←
     */
    private static void testCycleCase1(S22_Easy_141_环形链表 solution) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // 形成环，尾部连接到pos=1的节点

        System.out.println("创建链表: 3 → 2 → 0 → -4 → (连接到节点2)");
        boolean result = solution.hasCycle(node1);
        System.out.println("hasCycle() -> " + result + " (期望: true)");
        assert result : "应该检测到环";
        System.out.println("✓ 有环链表测试1通过");
    }

    /**
     * 测试有环链表 - [1,2] pos=0
     * 链表结构：1 → 2
     * ↑   ↓
     * ←---←
     */
    private static void testCycleCase2(S22_Easy_141_环形链表 solution) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);

        node1.next = node2;
        node2.next = node1; // 形成环，尾部连接到pos=0的节点

        System.out.println("创建链表: 1 → 2 → (连接到节点1)");
        boolean result = solution.hasCycle(node1);
        System.out.println("hasCycle() -> " + result + " (期望: true)");
        assert result : "应该检测到环";
        System.out.println("✓ 有环链表测试2通过");
    }

    /**
     * 测试无环链表 - [1] pos=-1
     */
    private static void testNoCycleCase1(S22_Easy_141_环形链表 solution) {
        ListNode node1 = new ListNode(1);
        // node1.next = null; (默认为null)

        System.out.println("创建链表: 1 → null");
        boolean result = solution.hasCycle(node1);
        System.out.println("hasCycle() -> " + result + " (期望: false)");
        assert !result : "不应该检测到环";
        System.out.println("✓ 无环链表测试1通过");
    }

    /**
     * 测试空链表
     */
    private static void testEmptyList(S22_Easy_141_环形链表 solution) {
        System.out.println("创建链表: null");
        boolean result = solution.hasCycle(null);
        System.out.println("hasCycle() -> " + result + " (期望: false)");
        assert !result : "空链表不应该有环";
        System.out.println("✓ 空链表测试通过");
    }

    /**
     * 测试单节点无环
     */
    private static void testSingleNodeNoCycle(S22_Easy_141_环形链表 solution) {
        ListNode node = new ListNode(42);

        System.out.println("创建链表: 42 → null");
        boolean result = solution.hasCycle(node);
        System.out.println("hasCycle() -> " + result + " (期望: false)");
        assert !result : "单节点无环不应该检测到环";
        System.out.println("✓ 单节点无环测试通过");
    }

    /**
     * 测试单节点有环（self-loop）
     */
    private static void testSingleNodeWithCycle(S22_Easy_141_环形链表 solution) {
        ListNode node = new ListNode(1);
        node.next = node; // 指向自己，形成环

        System.out.println("创建链表: 1 → (指向自己)");
        boolean result = solution.hasCycle(node);
        System.out.println("hasCycle() -> " + result + " (期望: true)");
        assert result : "单节点自环应该检测到环";
        System.out.println("✓ 单节点有环测试通过");
    }

    /**
     * 测试长链表无环
     */
    private static void testLongListNoCycle(S22_Easy_141_环形链表 solution) {
        ListNode head = new ListNode(1);
        ListNode current = head;

        // 创建长链表 1→2→3→...→100→null
        for (int i = 2; i <= 100; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }

        System.out.println("创建链表: 1 → 2 → 3 → ... → 100 → null");
        boolean result = solution.hasCycle(head);
        System.out.println("hasCycle() -> " + result + " (期望: false)");
        assert !result : "长链表无环不应该检测到环";
        System.out.println("✓ 长链表无环测试通过");
    }

    /**
     * 测试长链表有环
     */
    private static void testLongListWithCycle(S22_Easy_141_环形链表 solution) {
        ListNode head = new ListNode(1);
        ListNode current = head;
        ListNode cycleStart = null; // 记录环的起始节点

        // 创建长链表 1→2→3→...→100，在第50个节点开始环
        for (int i = 2; i <= 100; i++) {
            current.next = new ListNode(i);
            current = current.next;
            if (i == 50) {
                cycleStart = current; // 第50个节点作为环的起始点
            }
        }
        current.next = cycleStart; // 第100个节点连接到第50个节点，形成环

        System.out.println("创建链表: 1 → 2 → ... → 100 → (连接到节点50)");
        boolean result = solution.hasCycle(head);
        System.out.println("hasCycle() -> " + result + " (期望: true)");
        assert result : "长链表有环应该检测到环";
        System.out.println("✓ 长链表有环测试通过");
    }

    /**
     * 测试环在链表开头
     */
    private static void testCycleAtHead(S22_Easy_141_环形链表 solution) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);

        node1.next = node2;
        node2.next = node3;
        node3.next = node1; // 连接到头节点，形成环

        System.out.println("创建链表: 1 → 2 → 3 → (连接到节点1)");
        boolean result = solution.hasCycle(node1);
        System.out.println("hasCycle() -> " + result + " (期望: true)");
        assert result : "环在开头应该检测到环";
        System.out.println("✓ 环在开头测试通过");
    }

    /**
     * 测试环在链表末尾（相邻两个节点形成环）
     */
    private static void testCycleAtTail(S22_Easy_141_环形链表 solution) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node4; // 最后两个节点形成环

        System.out.println("创建链表: 1 → 2 → 3 → 4 → 5 → (连接到节点4)");
        boolean result = solution.hasCycle(node1);
        System.out.println("hasCycle() -> " + result + " (期望: true)");
        assert result : "环在末尾应该检测到环";
        System.out.println("✓ 环在末尾测试通过");
    }
}
